package 每日一题;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 658. 找到 K 个最接近的元素
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 *
 * 整数 a 比整数 b 更接近 x 需要满足：
 *
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 *
 *
 * 示例 1：
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 * 示例 2：
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
 * 输出：[1,2,3,4]
 *
 *
 * 提示：
 *
 * 1 <= k <= arr.length
 * 1 <= arr.length <= 104
 * arr 按 升序 排列
 * -104 <= arr[i], x <= 104
 */
public class D220825_T0658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 转为集合
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }

        // 与x 差值越小 的数排到前面
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o1 - x) - Math.abs(o2 - x);
            }
        });

        // 取前K 个数
        List<Integer> subList = list.subList(0, k);
        // 前K 个数 从小到大排序
        subList.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        return subList;

    }

    public static void main(String[] args) {
        D220825_T0658 d220825_t0658 = new D220825_T0658();
        d220825_t0658.findClosestElements(new int[]{1, 2, 3, 4, 5}, 4, 3);
    }
}
